#include <bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
// 这样定义INF的好处是: INF <= INF+x
const int N = 3e5 + 2;
struct edge//结构体
{
  int from, to;
  long long w; // 起点，终点，权值。起点from并没有用到，e[i]的i就是from
  edge(int a, int b, long long c)//结构函数
  {
    from = a;
    to = b;
    w = c;
  }
};
vector<edge> e[N]; // 用于存储图
struct s_node
{
  int id;
  long long n_dis; // id：结点；n_dis：这个结点到起点的距离
  s_node(int b, long long c)
  {
    id = b;
    n_dis = c;
  }
  bool operator<(const s_node &a) const
  {
    return n_dis > a.n_dis;
  }
};
int n, m;
int pre[N]; // 记录前驱结点，用于生成路径
void print_path(int s, int t)
{ // 打印从s到t的最短路
  if (s == t)
  {
    printf("%d ", s);
    return;
  }                      // 打印起点
  print_path(s, pre[t]); // 先打印前一个点
  printf("%d ", t);      // 后打印当前点。最后打印的是终点t
}
long long dis[N]; // 记录所有结点到起点的距离
void dijkstra()
{
  int s = 1;    // 起点s是1
  bool done[N]; // done[i]=true表示到结点i的最短路径已经找到
  for (int i = 1; i <= n; i++)
  {
    dis[i] = INF;
    done[i] = false;
  }                          // 初始化
  dis[s] = 0;                // 起点到自己的距离是0
  priority_queue<s_node> Q;  // 优先队列，存结点信息
  //优先队列从大到小排序
  Q.push(s_node(s, dis[s])); // 起点进队列
  while (!Q.empty())
  {
    s_node u = Q.top(); // pop出距起点s距离最小的结点u
    Q.pop();
    if (done[u.id])
      continue; // 丢弃已经找到最短路径的结点。即集合A中的结点
    done[u.id] = true;
    for (int i = 0; i < e[u.id].size(); i++)
    {                      // 检查结点u的所有邻居
      edge y = e[u.id][i]; // u.id的第i个邻居是y.to
      if (done[y.to])
        continue; // 丢弃已经找到最短路径的邻居结点
      if (dis[y.to] > y.w + u.n_dis)
      {
        dis[y.to] = y.w + u.n_dis;
        Q.push(s_node(y.to, dis[y.to])); // 扩展新的邻居，放到优先队列中
        pre[y.to] = u.id;                // 如果有需要，记录路径
      }
    }
  }
  // print_path(s,n);          //如果有需要，打印路径: 起点1，终点n
}
int main()
{
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++)
    e[i].clear();
  while (m--)
  {
    int u, v, w;
    scanf("%d%d%lld", &u, &v, &w);
    e[u].push_back(edge(u, v, w));
    // e[v].push_back(edge(v,u,w));    //本题是单向道路
  }
  dijkstra();
  for (int i = 1; i <= n; i++)
  {
    if (dis[i] >= INF)
      cout << "-1 ";
    else
      printf("%lld ", dis[i]);
  }
}